package com.atwulidun.kmp04;

public class KMPMatch {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        System.out.println(kmpMatch(str1,str2));// 15
    }

    // KMP匹配方法，返回文本字符串匹配第一个字符的下标，若不匹配返回-1
    // str1为文本字符串，str2为模式字符串
    public static int kmpMatch(String str1, String str2) {
        // 通过模式字符串获取next数组
        int[] next = getNext(str2);
        // 初始化文本字符串指针
        int i = 0;
        // 初始化模式字符串指针
        int j = 0;
        while (i < str1.length() && j < str2.length()) {
            // 可以类比获取next数组的方法
            // j==-1说明找到头都找不到和文本字符串匹配的字符，因此模式字符串要从头开始，两个指针都要自增1
            // 如果模式字符串和目标字符串的当前字符匹配，那么两个指针都自增1，看下一个字符是否匹配
            if (j == -1 || str1.charAt(i) == str2.charAt(j)) {
                i++;
                j++;
            } else {
                // 递归查找跟文本字符串当前字符匹配的模式字符串字符
                // i不变，j进行回溯
                j = next[j];
            }
        }
        // 跳出while循环有三种情况：
        // 1.i < str1.length() && j == str2.length()
        // 2.i = str1.length() && j == str2.length()
        // 3.i = str1.length() && j < str2.length()
        // 前两种情况都是匹配成功了的，第三种情况匹配不成功
        if (j == str2.length()) {
            return i - j;
        } else {
            return -1;
        }
    }
    // 获取next数组的方法
    public static int[] getNext(String str) {
        // 首先创建一个跟传入字符串长度相同的数组
        int[] next = new int[str.length()];
        // 下面相当于是模式串前缀和后缀的自我匹配：
        // 把前缀当成是模式串，把后缀当成是文本串
        // 初始化next[0]，为固定值
        next[0] = -1;
        // 初始化模式串前缀(伪模式串)
        int k = -1;
        // 初始化模式串后缀(伪文本串)
        int j = 0;
        // 特别注意这里：j < str.length() - 1，因为下面有next[++j]，为了数组不越界，j <= str.length() - 2
        while (j < str.length() - 1) {
            // 若k==-1，说明k = next[k]递归到最后都没有能使得前后缀匹配，此时next[++j] = ++k = 0;
            // ++j是因为该位置存的是前面j+1个字符对应的最大长度，往右错了一个位
            // 举例：
            // j==0，后缀为str.charAt(0)，因为k==-1，故前后缀不匹配，next[++j] = ++k = 0，即next[1]==0
            // j==1，后缀为str.charAt(1)，前缀为str.charAt(0)，若前后缀不匹配，则k=next[k]，看更短的前后缀能不能匹配，
            // 若递归到k==-1都没能匹配，则next[++j] = ++k = 0；若能找到第一次找到一个k使得前后缀匹配，那么匹配的最大长度为k+1(不断递归最大长度减小)
            // 此时也有next[++j] = ++k
            if (k == -1 || str.charAt(k) == str.charAt(j)) {
                k++;
                j++;
                // 小优化：
                // 下面要特别注意：若存在str.charAt(j)==str.charAt(k)的情况，那么先将当前k缓存一下，int k'=k，k'=next[k']一直递归下去，直到使得str.charAt(j)!=str.charAt(k')
                // 如果很不幸，str.charAt(j)==str.charAt(k')始终成立，那就当next[tempK]==-1时跳出while循环吧！
                // 为什么要递归找呢？因为str.charAt(j)跟文本字符串不匹配，那么就要看str.charAt(next[j])跟文本字符串匹不匹配，若str.charAt(j)==str.charAt(next[j])，那肯定是不匹配的啊，
                // 此时又要再看str.charAt(next[next[j]])跟文本字符串匹不匹配，若str.charAt(j)==str.charAt(next[next[j]])，那肯定也是不匹配的，依次类推............
                int tempK = k;
                while (next[tempK] != -1 && str.charAt(j) == str.charAt(tempK)) {
                    tempK = next[tempK];
                }
                // 跳出循环后无非就是找到了目标tempK，或是没找到，此时tempK==0
                next[j] = tempK;
            } else {
                // 递归找长度更小的匹配前后缀
                k = next[k];
            }
        }
        return next;
    }
}
